package Ep06_BinaryTree.BT23_0098;

import Ep06_BinaryTree.TreeNode;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/6/14 11:05
 * 说明：
 *      0098 验证一个树是不是二叉搜索树BST —— 递归解法
 * 思路：
 *      依然是中序遍历，观察是否是严格升序
 */

public class Better {
    private TreeNode max;
    public boolean isValidBST(TreeNode root) {
        // 如果能判断到叶子节点的下一个节点，说明整个路径都没问题，就可以返回了
        if (root == null) return true;

        // 中序遍历：左
        boolean left = isValidBST(root.left);
        if (!left) return false;    // 只有当前节点的左子树是一棵BST时，才会执行中序遍历的中间节点

        // 中序遍历：中
        // 判断：
        //      如果max节点还不为空，
        //      同时当前节点的值比max的小或相等，说明不满足BST中的“左子树都的节点都小于根节点”条件，返回false
        if (max != null && root.val <= max.val) return false;
        max = root; // 不断移动当前标记的最大BST子树的root节点

        // 中序遍历：右
        boolean right = isValidBST(root.right);
        if (!right) return false; // 只有当前接点的右子树是一棵BST时，才会认定为true
        return true;
    }
}
